package wh.多数元素;

import java.util.*;


/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/4/14 21:37
 * @description:给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr = {1,2,2,7,2,1,5,6,2,2,2};
        int i = majorityElement3(arr);
        System.out.println(i);
    }
    //解法1 hashmap
    public static int majorityElement(int[] nums) {
        int length = nums.length;
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i <= length - 1; i++) {
            if(map.containsKey(nums[i])){
                Integer m = map.get(nums[i]);
                m++;
                map.put(nums[i],m);
            }else {
                map.put(nums[i],1);
            }
        }
        Collection<Integer> values = map.values();
        Integer max = Collections.max(values);
        Set<Integer> set = map.keySet();
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()){
            Integer key = iterator.next();
            if(map.get(key) == max){
                return key;
            }
        }
        return 0;
    }
    //解法2 如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，则中间的那个数肯定为众数
    public static int majorityElement2(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    //解法3 投票法 利用多数元素和其他元素能两两抵消，抵消到最后肯定还剩余至少一个多数元素
    public static int majorityElement3(int[] nums) {
        int cand_num = nums[0], count = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (cand_num == nums[i])
                ++count;
            else if (--count == 0) {
                cand_num = nums[i];
                count = 1;
            }
        }
        return cand_num;
    }
    //投票法
    public static int majorityElement4(int[] nums) {
        int ret = 0;
        int counter = 0;
        for (int i = 0; i <= nums.length - 1; i++) {
            if (counter == 0) {
                ret = nums[i];
                counter = 1;
            } else if (nums[i] == ret) {
                counter++;
            } else {
                counter--;
            }
        }
        return ret;
    }



}
